package cn.edu.kmust.tdsc.jbmdiff;

import java.util.Hashtable;

public class BMCompressor {
	/**
	 * BM Escape byte, Do *NOT* change
	 */
	private static final byte BM_ESC = (byte) 0xfe;
	
	private static final int BM_B = 256;
	
	private BMCompressor() {};
	
	/**
	 * Compute x^n % m
	 * @param x base
	 * @param n exponentiation
	 * @param m modular
	 * @return x^n % m
	 */
	public static long powerMod(long x, long n, long m) {
		if (n == 0)
			return 1;
		if (n == 1)
			return x % m;
		long sqr = (x * x) % m;
		long pow = powerMod(sqr, n / 2, m);
		if ((n & 1) != 0)
			return (pow * x) % m;
		return pow % m;
	}

	private static final int getIntLength(int n) {
		// TODO Int length can be more than four
		if (n > 0xFFFFFF) {
			return 0x04;
		} else if (n > 0xFFFF) {
			return 0x03;
		} else if (n > 0xFF) {
			return 0x02;
		} else if (n >= 0) {
			return 0x01;
		}
		return 0x00;
	}
	
	private static final int writeInt(int n, byte[] out, int outPos) {
		// TODO Int length can be more than four
		if (n > 0xFFFFFF) {
			out[outPos++] = (byte) (n >> 24);
			out[outPos++] = (byte) (n >> 16);
			out[outPos++] = (byte) (n >> 8);
			out[outPos++] = (byte) n;
		} else if (n > 0xFFFF) {
			out[outPos++] = (byte) (n >> 16);
			out[outPos++] = (byte) (n >> 8);
			out[outPos++] = (byte) n;
		} else if (n > 0xFF) {
			out[outPos++] = (byte) (n >> 8);
			out[outPos++] = (byte) n;
		} else if (n >= 0) { 
			out[outPos++] = (byte) n;
		}
		return outPos;
	}
	
	private static final int encode(int position, int length, byte[] out, int outPos) {
		out[outPos++] = BM_ESC;
		int posWidth = getIntLength(position);
		int lenWidth = getIntLength(length);
		// the byte: (1) prevent from 0xfe; (2) record 2 widths
		out[outPos++] = (byte) ((posWidth << 4) | lenWidth);
		outPos = writeInt(position, out, outPos);
		outPos = writeInt(length, out, outPos);
		return outPos;
	}
	
	/**
	 * Compresses the Input Bytes
	 * @param in Input Bytes
	 * @param block Block Size
	 * @param prime A Large Prime
	 * @param out Compressed Results
	 */
	public static int compress(final byte[] in, final int block, final long prime, byte[] out) {
		// declarations
		final int len = in.length;  // input length
		final int end = len - block;  // end of the in
		final long h = powerMod(BM_B, block - 1, prime);
		long fp = 0;  // fingerprint
		int outPos = 0;  // pointer of out
		int i = 0;
		int j = 0;
		int k = 0;
		int lastEncode = 0;  // the last time where input
		int greedyLen = 0;  // greedy searching length
		int cp = 0;  // current pointer
		int pp = 0;  // previous pointer
		int blockLen = 0;  // block length to encode
		Integer position = null;
		int blockEnd = 0;  // current block ending position
		// TODO use a light wrapper which allows same keys
		Hashtable<Long, Integer> table = 
			new Hashtable<Long, Integer>(len / block * 2 + 1, 1.0f);
		
		// initialization, O(blockSize)
		fp = 0;
		for (i = 0; i < block; i ++) {
			fp = (BM_B * fp + (in[i] & 0xFF));
			fp %= prime;
		}
		table.put(fp, 0);
		
		// rolling hash, O(length)
		for (i = 1; i < end && lastEncode < len; i++) {
			// update fp
			fp = (BM_B * (fp - (in[i - 1] & 0xFF) * h) 
				+ (in[i + block - 1] & 0xFF)) % prime;
			if (fp < 0) {
				fp += prime;
				fp %= prime;
			}
			
			// try match
			if (i < lastEncode) {
				position = null;
			} else {
				position = table.get(fp);
			}
			if (null != position) {
				boolean match = true;
				// memcmp(), I don't know whether java has it
				blockEnd = i + block;
				for (j = i, k = 0; j <= blockEnd; j++, k++) {
					if (in[j] != in[position + k]) {
						// the possibility to reach here is 1/prime
						match = false;
						break;
					}
				}
				if (match) {
					// Greedily check for previous blockSize - 1
					cp = i;
					pp = position;
					blockLen = block;
					for (greedyLen = 0;
						pp > i - block + 1 && in[--cp] == in[--pp];
						greedyLen++);
					position -= greedyLen;
					blockLen += greedyLen;
					// encode literal
					while (lastEncode < i) {
						if (in[lastEncode] == BM_ESC) {
							out[outPos++] = BM_ESC; 
						}
						out[outPos++] = in[lastEncode++];
					}
					lastEncode += block;
					// Greedily check for next
					for (cp = i + block, pp = position + block, greedyLen = 0;
						cp < len && in[cp++] == in[pp++];
						greedyLen++, lastEncode++);
					blockLen += greedyLen;
					outPos = encode(position, blockLen, out, outPos);
				}
			}
			
			// save fp
			if (i % block == 0) {
				table.put(fp, i);
			}
		}  // end for
		
		// emit rest
		while (lastEncode < len) {
			if (in[lastEncode] == BM_ESC) {
				out[outPos++] = BM_ESC; 
			}
			out[outPos++] = in[lastEncode++];
		}
  		return outPos;
	}
}
